CODE 19. Flatten Binary Tree to Linked List

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/17/2013-09-17-CODE 19 Flatten Binary Tree to Linked List/

访问原文「CODE 19. Flatten Binary Tree to Linked List」

Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6

The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6

click to show hints.
Hints:If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

public void flatten(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return;
	}
	TreeNode newRoot = new TreeNode(0);
	TreeNode cpyRoot = newRoot;
	Stack<TreeNode> stack = new Stack<TreeNode>();
	stack.push(root);
	while (!stack.isEmpty()) {
		cpyRoot.right = stack.pop();
		cpyRoot.left = null;
		cpyRoot = cpyRoot.right;
		while (cpyRoot.left != null) {
			if (cpyRoot.right != null) {
				stack.push(cpyRoot.right);
			}
			cpyRoot.right = cpyRoot.left;
			cpyRoot.left = null;
			cpyRoot = cpyRoot.right;
		}
		if (cpyRoot.right != null) {
			stack.push(cpyRoot.right);
		}
	}
	root = newRoot.right;
}